permutation & combination

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数： | 阅读次数：

LeetCode next permutation

这道题的讨论区解答很详细， 特别注意一下 reverse(nums.begin(), nums.end()) 参数是迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    void nextPermutation (vector<int>& nums) {
        int n = nums.size();
        int k;
        int l;
        for (k = n - 2; k >= 0; k--) {
            if (nums[k] < nums[k + 1]) {
                break;
            }
        }
        if (k < 0) {
            reverse (nums.begin(), nums.end());
        } else {
            for (l = n - 1; l > k; l--) {
                if (nums[k] < nums[l]) {
                    break;
                }
            }
            swap (nums[k], nums[l]);
            reverse (nums.begin() + k + 1, nums.end());
        }

    }
};

LeetCode Permutation

使用 vector& 与 第二次swap

整个过程只存在一个nums,改变一个nums的操作，就相当于整个流程中的nums都做了相同的变化，因此需要在DFS后再进行一次交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>>res;
        DFS(res, nums, 0);
        return res;        
    }
    
    void DFS(vector<vector<int>>& res, vector<int>& nums, int pos){
        if(pos == nums.size()){
            res.push_back(nums);
            return;
        }
        for(int i = pos; i < nums.size(); i++){
            swap(nums[pos], nums[i]);
            DFS(res, nums, pos + 1);
            swap(nums[pos], nums[i]);
        }
    }
};

使用 传值 并去掉第二次的交换

每次调用DFS都会copy一个nums，因此不用担心调用DFS会对之前的nums有影响，也就不用在调用完递归函数后再进行交换了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>>res;
        DFS(res, nums, 0);
        return res;        
    }
    
    void DFS(vector<vector<int>>& res, vector<int> nums, int pos){
        if(pos == nums.size()){
            res.push_back(nums);
            return;
        }
        for(int i = pos; i < nums.size(); i++){
            swap(nums[pos], nums[i]);
            DFS(res, nums, pos + 1);
     
        }
    }
};
0%